Data in a semi-structured text format, such as XML (Extensible Markup Language), JSON (JavaScript Object Notation), or the like, has been used. There is available a method in which parentheses tree data comprising a BP (balanced parentheses) bit string is used as an index of data in the semi-structured text format. According to this method, an appropriate position of data is searched for by obtaining the position of a bit with an excess value for a search in a bit string. Non-Patent Literature 1 discloses a method in which semi-structured text data is used as a BP bit string.
In a search using this method, a block is searched for, using a minimum excess value or the like of each of a plurality of blocks obtained by dividing a bit string, and the position of a bit with an excess value for the search in a block is thereafter obtained. An algorithm in which the position of a bit satisfying a search condition in a block is checked sequentially beginning with the top bit takes time for processing. Non-Patent Literature 2 describes that a bit position is specified at a high speed by searching a look-up table generated in advance, using as a search key a combination of a bit string of a block and an excess value.